8.5 一些 Leetcode 例子

今天來拖點稿子，解幾題跟連通有關的題目吧。

Leetcode 1192. Critical Connections in a network

https://leetcode.com/problems/critical-connections-in-a-network/
題目大意：給定 n 個點的圖，找出所有的關鍵連線，也就是橋。

解法：首先觀察到，所有的橋都會在生成樹上，接下來我們只要用 lowpt(x) 來判斷哪一些是橋就可以啦。如果是橋的話，那麼子節點底下不存在任何回連邊回到祖先。

class Solution {
public:
    vector<vector<int>> criticalConnections(int n, vector<vector<int>>& connections) {
        vector<vector<int>> adj(n);
        for(auto e : connections) {
            adj[e[0]].push_back(e[1]);
            adj[e[1]].push_back(e[0]);
        }
        vector<vector<int>> ret;
        map<int, int> lowpt;
        function<void(int, int, int)> dfs = [&](int x, int p=-1, int d=0) {
            lowpt[x] = d;
            for(int y : adj[x]) {
                if (lowpt.find(y) == lowpt.end()) {
                    dfs(y, x, d+1);
                    if (lowpt[y] > d) {
                        ret.push_back({x, y});
                    }   
                }
                if (y != p) {
                    lowpt[x] = min(lowpt[x], lowpt[y]);
                }
            }
        };
        for (int i = 0; i < n; i++) if (lowpt.find(i) == lowpt.end()) {
            dfs(i, -1, 0);
        }
        return ret;
    }
};

Leetcode 1627. Graph Connectivity With Threshold

題目大意：給定一張圖 G，每個點的編號是從 1 到 n，若兩個點 a 和 b 的最大公因數超過 threashold，就會連一條邊。現在問很多問題，問兩個點是否屬於同一個連通元件。

解法：考慮每一個超過 threadshold 的數字，把所有的倍數都連起來。我們可以用併查集將這些倍數合併成同一組。

class Solution {
public:
    vector<bool> areConnected(int n, int threshold, vector<vector<int>>& queries) {
        vector<int> g(n+1);
        function<int(int)> Find = [&](int x) -> int {
            return g[x]==x? g[x] : (g[x]=Find(g[x]));
        };
        function<void(int, int)> Union = [&](int x, int y) {
            g[Find(x)] = Find(y);
        };
        for(int i=1;i<=n;i++) g[i] = i;
        for(int x=threshold+1;x<=n;x++)
            for(int y = x + x; y <= n; y += x)
                Union(y, y-x);
        vector<bool> ret;
        for(auto e : queries) {
            ret.push_back(Find(e[0])  == Find(e[1]));
        }
        return ret;
    }
};